﻿#pragma once
#include "Index.h"

class IBeautifulTowerII
{
public:
    virtual long long maximumSumOfHeights(std::vector<int>& maxHeights) = 0;
};

class BeautifulTowerII
{
public:
	class Solution:public IBeautifulTowerII
	{
	public:
		long long maximumSumOfHeights(std::vector<int>& maxHeights) override
		{
            if (maxHeights.empty())
                return 0;
            const int size = maxHeights.size();

            //用于统计山脉单边的单调栈结构
            std::stack<int> heightStack;
            std::stack<int> countStack;
            long long height_sum = 0;

            //以 i位置为峰值,含自身在内的山脉左边的高度和
            std::vector<long long> leftpeak(size, 0);
            for (int i = 0; i < size; ++i)
            {
                int peak = maxHeights[i];
                int count = 1;

                while (!heightStack.empty() && peak <= heightStack.top())
                {
                    count += countStack.top();
                    height_sum -= heightStack.top() * countStack.top();
                    heightStack.pop();
                    countStack.pop();
                }

                heightStack.push(peak);
                countStack.push(count);
                height_sum += peak * count;
                leftpeak[i] = height_sum;
            }

            heightStack = {};
            countStack = {};
            height_sum = 0;
            std::vector<long long> rightpeak(size, 0);
            for (int i = size - 1; i >= 0; --i)
            {
                int peak = maxHeights[i];
                int count = 1;

                while (!heightStack.empty() && peak <= heightStack.top())
                {
                    count += countStack.top();
                    height_sum -= heightStack.top() * countStack.top();
                    heightStack.pop();
                    countStack.pop();
                }

                heightStack.push(peak);
                countStack.push(count);
                height_sum += peak * count;
                rightpeak[i] = height_sum;
            }

            long long max_height_sum = 0;
            for (int i = 0; i < size; ++i)
            {
                long long height = leftpeak[i] + rightpeak[i] - maxHeights[i];
                max_height_sum =std::max<long long>(max_height_sum, height);
            }
            return max_height_sum;
		}
	};
};

#ifdef DEV_TEST
#include "gtest/gtest.h"

TEST(BeautifulTower, maximumSumOfHeights)
{
    TEST_SOLUTION1(IBeautifulTowerII, BeautifulTowerII::Solution, &)
    {
        auto maxHeights = TestingUtil::parseNums<int>("[6,5,3,9,2,7]");
        solution->maximumSumOfHeights(maxHeights);
    };
}
#endif